package xinhao.lr.lr1;

import xinhao.*;
import java.util.*;

/**
 * @author by xinhao  2021/8/24
 */
public class LR1Utils {

    /**
     *  求解等价项目的集合
     * 对于任何 S -> [a•Bb, a] 的项目，因为圆点后面的是非终结符，
     * 那么这个非终结符 B 的产生式 B -> b B ->c, 且文法符号串`ba` 的串首符号集就是[b]
     * 对应的移入项目组  B -> [•b, b] B -> [•c, b]  都是相同项目，加入同一个项目集。
     * closure 方法就是计算项目集
     * @param items
     * @param grammar
     * @return
     */
    private static Set<ProductionItem> closure(Set<ProductionItem> items, Grammar grammar) {
        // 所有等价项目集合
        Set<ProductionItem> resultItems = new HashSet<>(items);
        Stack<ProductionItem> stack = new Stack<>();
        // 先将传入的items添加到栈里面
        stack.addAll(items);
        // 栈不为空，说明还有项目没有遍历到
        while (!stack.isEmpty()) {
            ProductionItem item = stack.pop();
            Symbol posSymbol = item.getPosSymbol();
            /**
             * 当前项目圆点位置是非终结符，那么这个非终结符的产生式组对应的移进项目和当前项目属于一个闭包
             */
            if (!posSymbol.isTerminator()) {
                // 非终结符对应的产生式组
                List<Production> posSymbolProductions = grammar.getProductionsMap().get(posSymbol);
                /**
                 * 获取非终结符后面的文符号串，再加上当前项目展望符得到的文法符号串
                 * 例如 当前项目[a•Bb, a], 那么keySymbols就是 [ba]
                 */
                List<Symbol> keySymbols = item.getFirstKeysSymbols();
                // 获取串首终结符集
                Set<Symbol> firstSymbols = grammar.getFirstsSetByKeys(keySymbols).getSet();

                /**
                 * 要进行两次循环，得到所有的等价项目
                 */
                for (Production production : posSymbolProductions) {
                    for (Symbol symbol : firstSymbols) {
                        ProductionItem newItem = ProductionItem.createByProduction(production, symbol);
                        if (!resultItems.contains(newItem)) {
                            resultItems.add(newItem);
                            stack.push(newItem);
                        }
                    }
                }
            }
        }

        return resultItems;
    }

    // 为 Goto 创建一个缓存 table，这样就只需要求解一次
    public static final Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> GOTO_TABLE = new HashMap<>();
    private static ProductionItemSet Goto(ProductionItemSet itemSet, Symbol symbol, Grammar grammar) {
        // 如果缓存里有，那么直接返回，不用再求解了
        if (GOTO_TABLE.containsKey(itemSet)) {
            Map<Symbol, ProductionItemSet> map = GOTO_TABLE.get(itemSet);
            if (map.containsKey(symbol)) {
                return map.get(symbol);
            }
        }

        // 当前项目集 itemSet 遇到符号 symbol 的后继项目集合
        Set<ProductionItem> nextItems = new HashSet<>();
        for (ProductionItem item : itemSet.getItems()) {
            /**
             * 项目pos点的符号与 symbol 是否相同
             * 即项目 [a•Bb, a] 匹配 符号B
             * 后继项目就是 [aB•b, a]
             */
            if (item.getPosSymbol().equals(symbol)) {
                nextItems.add(ProductionItem.createNextByItem(item));
            }
        }
        // 如果nextItems为空，说明当前项目集没有 符号symbol的后继项目
        if (nextItems.isEmpty()) {
            return null;
        }
        // 创建后继项目集
        ProductionItemSet nextItemSet = ProductionItemSet.create(closure(nextItems, grammar));
        // 存放到缓存中
        Utils.addToDoubleMap(GOTO_TABLE, itemSet, symbol, nextItemSet);
        return nextItemSet;
    }

    /**
     * 得到当前文法所有的项目集
     * @param grammar
     * @return
     */
    private static List<ProductionItemSet> getAllItemSet(Grammar grammar) {
        // 开始符号对应的产生式
        Production startProduction = grammar.getProductionsMap().get(grammar.getStart()).get(0);
        // 开始符号对应的项目
        ProductionItem startItem = ProductionItem.createByProduction(startProduction, Symbol.END);
        // 开始符号对应的项目集，也是第一个项目集
        ProductionItemSet startItemSet = ProductionItemSet.create(closure(Utils.asSet(startItem), grammar));

        // 文法中所有符号，包括终结符和非终结符，但是不包括结束符号 END
        Set<Symbol> allSymbols = grammar.getAllSet();
        // 当前文法所有的项目集
        List<ProductionItemSet> allItemSets = new ArrayList<>();
        allItemSets.add(startItemSet);
        Stack<ProductionItemSet> stack = new Stack<>();
        stack.push(startItemSet);
        while (!stack.isEmpty()) {
            ProductionItemSet itemSet = stack.pop();
            // 遍历所有符号
            for (Symbol eachSymbol : allSymbols) {
                // 当前项目集遇到字符eachSymbol得到后继项目集
                ProductionItemSet gotoItemSet = Goto(itemSet, eachSymbol, grammar);
                /**
                 * 如果得到的后继项目集gotoItemSet 在allItemSetList中没有，
                 * 那么代表它是全新的，那么添加进行。
                 */
                if (gotoItemSet != null && !allItemSets.contains(gotoItemSet)) {
                    allItemSets.add(gotoItemSet);
                    // 新的项目集要添加到栈中，进行遍历
                    stack.push(gotoItemSet);
                }
            }
        }
        return allItemSets;
    }

    /**
     * 得到文法对应的 LR1 分析表 actionMap 和 gotoMap
     * @param grammar
     * @param allItemSetList
     * @param actionMap
     * @param gotoMap
     */
    private static void createLR1Table(Grammar grammar, List<ProductionItemSet> allItemSetList,
                                       Map<ProductionItemSet, Map<Symbol, Action>> actionMap,
                                       Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap) {
        // 开始符号
        Symbol start = grammar.getStart();

        // 遍历文法所有的项目集
        for (ProductionItemSet itemSet : allItemSetList) {
            // 遍历项目集中的项目
            for (ProductionItem item : itemSet.getItems()) {
                // 得到当前项目 pos 位置的符号
                Symbol posSymbol = item.getPosSymbol();
                // 如果是非终结符，那么就要添加到 gotoMap 中
                if (!posSymbol.isTerminator()) {
                    ProductionItemSet gotoItemSet = Goto(itemSet, posSymbol, grammar);
                    Utils.addToDoubleMapPrintConflict(gotoMap, itemSet, posSymbol, gotoItemSet,
                            "gotoMap 有冲突 old:%s  new:%s");
                } else {
                    // 是终结符但不是结束符号 END
                    if (!Symbol.END.equals(posSymbol)) {
                        // 获取后继项目集
                        Action action = Action.createS(Goto(itemSet, posSymbol, grammar));
                        // 想 action 中添加移入操作action
                        Utils.addToDoubleMapPrintConflict(actionMap, itemSet, posSymbol, action,
                                "actionMap 有冲突 old:%s  new:%s");
                    } else {
                        // 当前项目是 [aBb•, a] 格式，说明需要归约，这个就是归约需要的产生式
                        Production production = item.getProduction();
                        // 如果产生式左部和开始符号相同，说明是总结了，添加 acc 的action
                        if (start.equals(production.getLeft())) {
                            Action action = Action.createAcc();
                            Utils.addToDoubleMapPrintConflict(actionMap, itemSet, posSymbol, action,
                                    "actionMap 有冲突 old:%s  new:%s");
                        } else {
                            /**
                             * 在LR1 算法中，只有遇到当前项目的展望符才进行归约
                             */
                            Action action = Action.createR(production);
                            Utils.addToDoubleMapPrintConflict(actionMap, itemSet, item.getExpectSymbol(), action,
                                    "actionMap 有冲突 old:%s  new:%s");
                        }
                    }
                }
            }
        }
    }

    /**
     * 判断文法能否匹配这个输入符号串inputSymbols
     * @param inputSymbols
     * @param startState
     * @param actionMap
     * @param gotoMap
     * @return
     */
    private static boolean match(List<Symbol> inputSymbols, ProductionItemSet startState,
                                 Map<ProductionItemSet, Map<Symbol, Action>> actionMap,
                                 Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap) {
        // 匹配的产生式列表
        List<Production> matchProductions = new ArrayList<>();
        // 状态栈
        Stack<ProductionItemSet> stateStack = new Stack<>();
        // 放入开始状态，即开始项目集
        stateStack.push(startState);
        // 符号栈
        Stack<Symbol> symbolStack = new Stack<>();
        // 先放入结束符号$
        symbolStack.push(Symbol.END);

        // 表示读取输入符号的位置
        int inputPos = 0;
        while (true) {
            // 当前状态栈栈顶状态
            ProductionItemSet currentItemSet = stateStack.peek();
            // 当然输入字符
            Symbol inputSymbol = inputSymbols.get(inputPos);
            // 获取当前栈顶状态遇到输入符号得到的 action
            Action action = actionMap.get(currentItemSet).get(inputSymbol);
            // 如果是 acc
            if (action.isAcc()) {
                // 当输入字符是最后一个字符，表示匹配成功。否则输入字符还没有匹配完成，匹配失败
                if (inputPos == inputSymbols.size() -1) {
                    System.out.println("匹配成功");
                    System.out.println(matchProductions);
                    return true;
                }
                System.out.println("匹配失败");
                System.out.println(matchProductions);
                return false;
            } else if (action.isS()) {
                // 移入操作
                stateStack.push(action.getStateItemSet());
                symbolStack.push(inputSymbol);
                // 下一个输入字符
                inputPos ++;
            } else if (action.isR()){
                // 归约操作的产生式
                Production production = action.getProduction();
                int size = production.getRight().size();
                // 记录一下状态栈弹出的状态
                List<Integer> popStateList = new ArrayList<>();
                // 记录一下弹出的字符
                List<Symbol> popSymbol = new ArrayList<>();
                // 根据产生式右部的字符数量，从状态栈和字符栈中弹出对应数量的元素
                for (int index = 0; index < size; index++) {
                    popStateList.add(stateStack.pop().getState());
                    popSymbol.add(symbolStack.pop());
                }
                System.out.println("popStateList: " + popStateList + "  popSymbol:"+popSymbol+"  production:"+production);
                // 添加归约的产生式
                matchProductions.add(production);

                // 将产生式左部添加到字符栈
                symbolStack.push(production.getLeft());
                // 获取这个字符在 gotoMap 中对应的状态，添加到状态栈
                ProductionItemSet itemSet = gotoMap.get(stateStack.peek()).get(production.getLeft());
                stateStack.push(itemSet);
            } else {
                throw new RuntimeException("匹配错误");
            }
        }
    }

    public static void main(String[] agrs) {
        Symbol start = Alphabet.addSymbol("S'");
        Grammar grammar = Grammar.create(start,
                Production.create(start, "S"),
                Production.create(Alphabet.getSymbol("S"), "BB"),
                Production.create(Alphabet.getSymbol("B"), "aB"),
                Production.create(Alphabet.getSymbol("B"), "b")
        );

        List<ProductionItemSet> allItemSetList = getAllItemSet(grammar);

        System.out.println(allItemSetList);

        Map<ProductionItemSet, Map<Symbol, Action>> actionMap = new HashMap<>();
        Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap = new HashMap<>();
        createLR1Table(grammar, allItemSetList, actionMap, gotoMap);

        List<Symbol> inputSymbols = Utils.createSymbolsByString("bab");
        inputSymbols.add(Symbol.END);
        match(inputSymbols, allItemSetList.get(0), actionMap, gotoMap);
    }

}
